/*
 * 求任意两点间的最短路，使用Floyd，而无需使用n次Dijkstra
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1000;
const int INF=1000001;
//节点数N和边数M
int N,M;
int map[MAXN][MAXN];
int path[MAXN][MAXN];
//初始化
void init(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			map[i][j]=INF;
			path[i][j]=0;
		}
	}
}
//弗洛伊德算法
void floyd(){
	for(int k=1;k<=N;k++){
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				//不记录路径
				//map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
				if(map[i][j]>map[i][k]+map[k][j]){
					map[i][j]=map[i][k]+map[k][j];
					path[i][j]=path[i][k];
				}
			}
		}
	}
}
int main(void){
	int u,v,d;
	scanf("%d%d",&N,&M);
	init();
	while(M--){
		scanf("%d%d%d",&u,&v,&d);
		map[u][v]=map[v][u]=d;
	}
	floyd();
	//询问最短路径及权值和
	while(scanf("%d%d",&u,&v)!=EOF){
		int t=u;
		printf("%d",u);
		while(t!=v){
			printf("-->%d",path[t][v]);
			t=path[t][v];
		}
		printf("\ncost: %d\n",map[u][v]);
	}
	return 0;
}
